Viterbi decoding is a technique in which a data sequence encoded by a certain convolution operation is received and then the received data is decoded by predicting the most suitable data sequence according to the rules of the convolution operation. Rules of a convolution operation can be described as a state transition diagram. And if time concept is added to the state transition diagram, a trellis diagram can be described.
FIG. 9 shows the structure of a convolution encoder typically used in Gigabit Ethernet (Ethernet: trademark). The convolution encoder, which includes delay elements 101, 102, and 103 and adders 104 and 105, is a 2-bit input, 8-state convolution encoder. The delay elements 101, 102, and 103 delay an input value by one clock and output the delayed value. The adder 104 adds the output of the delay element 101 and the higher-order bit of input data. The delay element 102 receives the result of the addition from the adder 104. The adder 105 adds the output of the delay element 102 and the lower-order bit of the input data. The delay element 103 receives the result of the addition from the adder 105. And the delay element 101 receives the output of the delay element 103. By this process, the delay elements 101 to 103 indicate 3-bit states, i.e., 8 states.
FIG. 10 is a trellis diagram for the convolution encoder. The trellis diagram shows transitions occurring with respect to states S0, S1, S2, S3, S4, S5, S6, and S7 from time (k−1) to time k and from the time k to time (k+1). The lines connecting the states are called branches. Each branch connects one state to another which is a transition destination from that one state.
In Viterbi decoding, in order to evaluate the likelihood, i.e., the probability, of a transition from each state, a “branch metric” is calculated for each branch by using an evaluation function. A branch metric is usually calculated as a square error between an ideal value and an actually received value. On the other hand, for each state, the cumulative sum of the branch metrics for the most likely branches of all branches that can reach that state is stored from the start of the decoding. This sum value is called a path metric. In Viterbi decoding, a branch for which the result of adding the path metric at the time (k−1) and the branch metric at the time k is the smallest is determined as the most likely branch. That is, an ACS circuit is an Add-Compare-Select circuit which performs additions of the path metrics at the time (k−1) and the branch metrics at the time k, compares the results of the additions, and selects the most likely branches, so as to determine the most likely branches.
Paths created by connecting the most likely branches obtained at each time are called survivor paths. In the trellis diagram, each state has its own survivor path. However, as the decoding process proceeds, the survivor paths of all states converge into one. The one survivor path thus obtained is the final decoding result produced by the Viterbi decoding.
A conventional ACS circuit uses square calculations for calculating branch metrics. This causes a problem in that the circuit is complicated and an overflow occurs because each path metric is the sum total of the branch metrics. As a measure to prevent the occurrence of path metric overflows, a technique has been known, in which the values of path metrics are occasionally monitored and at a point in time when an overflow is likely to occur, the same value is subtracted from the path metric values of the respective states. In this technique, however, after the ordinal processing is performed by the ACS circuit, the overflow determination and the subtracting processing are necessary, causing decrease in the processing rate. Therefore, a technique has been developed, in which squared terms are deleted in the branch metric calculation by using differential branch metrics (hereinafter referred to as “DBMs”), each of which is a difference between branch metrics, thereby simplifying the calculation, while an overflow is avoided in the path metric calculation by using differential path metrics (hereinafter referred to as “DPMs”), each of which is a difference between path metrics (see Patent Document 1, for example).
Nevertheless, in the ACS circuit in which path selections are made according to the metric differences as described above, since a relatively large number of DPMs must be retained, a retaining circuit of relatively large size is required. For example, in the case of the 8-state trellis diagram, the number of path metrics is eight, while the number of DPMs is twenty-eight (=8C2). Therefore, in order to suppress the increase in the size of the retaining circuit, an ACS circuit in which the number of DPMs to be retained is limited has been developed (see Non-Patent Document 1, for example). This ACS circuit, however, uses typical branch metrics in addition to DBMs in calculating the DPMs and thus has a problem in that square calculations are necessary.
Patent Document 1: Japanese Patent No. 3258174 specifications
Non-Patent Document 1: Akira Yamamoto, et al, “A 500 MHz 50 mW Viterbi Detector for DVD Systems using Simplified ACS and New Path Memory Architecture”, 2002 Symposium On VLSI Circuits Digest of Technical Papers, pp. 256-259